package com.LeeCode;

/**
 * 使差值相等的最少数组改动次数
 */

public class Code3224 {
    public static void main(String[] args) {
        int[] nums = {1, 0, 1, 2, 4, 3};
        int k = 4;
        System.out.println(new Code3224().minChanges(nums, k));
    }

    public int minChanges(int[] nums, int k) {
        int[] cnt = new int[k + 1];
        int[] cnt2 = new int[k + 1];
        int n = nums.length;
        for (int i = 0; i < n / 2; i++) {
            int p = nums[i];
            int q = nums[n - 1 - i];
            if (p > q) { // 保证 p <= q
                int tmp = p;
                p = q;
                q = tmp;
            }
            cnt[q - p]++;
            cnt2[Math.max(q, k - p)]++;
        }

        int ans = n;
        int sum2 = 0; // 统计有多少对 (p,q) 都要改
        for (int x = 0; x <= k; x++) {
            // 其他 n/2-cnt[x] 对 (p,q) 至少要改一个数，在此基础上，有额外的 sum2 对 (p,q) 还要再改一个数
            ans = Math.min(ans, n / 2 - cnt[x] + sum2);
            // 对于后面的更大的 x，当前的这 cnt2[x] 对 (p,q) 都要改
            sum2 += cnt2[x];
        }
        return ans;
    }

    // 差分做法
    public int minChanges1(int[] nums, int k) {
        int n = nums.length;
        int[] d = new int[k + 2];
        for (int i = 0; i < n / 2; i++) {
            int p = nums[i];
            int q = nums[n - 1 - i];
            if (p > q) { // 保证 p <= q
                int tmp = p;
                p = q;
                q = tmp;
            }
            int x = q - p;
            int mx = Math.max(q, k - p);
            // [0, x-1] 全部 +1：把 q-p 改成小于 x 的，只需要改 p 或 q 中的一个数
            d[0]++;
            d[x]--;
            // [x+1, mx] 全部 +1：把 q-p 改成大于 x 小于等于 mx 的，也只需要改 p 或 q 中的一个数
            d[x + 1]++;
            d[mx + 1]--;
            // [mx+1, k] 全部 +2：把 q-p 改成大于 mx 的，p 和 q 都需要改
            d[mx + 1] += 2;
        }

        int ans = n;
        int minModify = 0;
        for (int v : d) {
            minModify += v;
            ans = Math.min(ans, minModify);
        }
        return ans;
    }
}
